%Notes:
% anytime a \begin{thing} is used, there needs to be a corresponding \end{thing}
% double quotes are done by using two single quotes

%states the different types of class
%article is being used because of the weird numbering system on the other
%classes, so titlepage has to explicitly stated in this class
\documentclass[titlepage]{article}

%this says to use times as a style and to indent the first paragraph because it 
%does not do that by default
\usepackage{times, indentfirst}

%this allows graphics to be added
\usepackage[pdftex]{graphicx}

%this package is to allow the following \restylefloat which is an override
%that allows the user to explicity state formatting with figures (images)
\usepackage{float}
\restylefloat{figure}

%the following three lines are all for the title and the various \huge, etc are different font
%sizes and there is a difference between \Huge and \huge
%\\* is the escape for new line
\title{\Huge CSE325 Lab 3 Scheduler}
\author{\huge Group 4: \\*  \LARGE Matthew Cramer, Jesse Martinez, Marc Mendoza}
\date{\LARGE \today}

%needed to start the document, think of it like main in normal programming
\begin{document}
%creates the title page based on \title, \author, \date
\maketitle

%this labels a section and it will be numbered in the paper, there is a hierarchy to
%the levels of sections, and curly braces are required
\section{Introduction}
%text can be placed anywhere and it will show up when compiled
In this lab, the goal is to design a Scheduler that will manage how processes are run inside an Operating System. The Process Manager will be used in this program to manage the five queues that represent the states of the processes called: new, ready, running, waiting and terminate. The queues will be manipulated by the Queue Manager still that will be called from the Process Manager. This documentation will describe two major aspects to this assignment: The changes inside the Process Manager that will be called from the Scheduler and how the Scheduler will be constructed and run with the Testing Interface. The Process Control Block will also be described and the changes to it in order to accommodate the Scheduler.  

The scheduler will contain two algorithms: Fair Share Group, that will give equal time to a process in the same group and equal time to all the groups, and Priority, which will assign priorities to processes giving running time to the highest priority process first.  The implementation of these algorithms will be described as well as the relationship between the Scheduler and Process Manager.  This documentation will also describe the test cases that will be run on the program to ensure its robustness as well as an analysis of the run time for the program.

\section{How to Run Program}
To compile the program, run the following script in the TestingInterface Directory:

compile.sh

To run the program, type in one of the following(Be sure to run in the TestingInterface Directory):

User Interface:

./run

Test Modules*:

./run [Test-MaxAll | Test-Priority | Test-FS].txt

*Note:  For the input file, the Testing Interface contains a bug where if there is not a space at the end of the line in the input file, the program will go into an infinite loop due to reading in the new line character.  To create a test file for the program, be sure to leave a space after each line in order to have the program correctly identify the command.

\section{Process Control Block}
%\subsection is one level below section on the hierarchy
\subsection{Valid Bit}
This bit is used for determining if the data in this queue struct is valid or not.  Since each queue will be handling a lot of processes, we are assuming that a lot of processes will be enqueued and dequeued from the queues and to save clock cycles.  This valid bit will tell the queue manager that this slot in memory is free to use, rather than erasing the memory contents from that cell which will take time.

\subsection{Process ID}
This element will store the process ID for the current process.  This number will be unique for the whole operating system. A counter is incremented and is used as the pid when there are no pids before the counter that are available to be used as a unique pid. In order to keep track of available pids before the counter, the pid of a process that has terminated will be stored on the Terminate queue. Then when a new process is made, the oldest entry in the terminate Queue is taken out and used as the new process’ pid. If the counter reaches a limit and there are no processes in the terminate Queue, the process manager returns an error. This method is done in order to reuse old pids while limiting the amount of memory is used.

\subsection{Program Status Word}
The PSW will hold information relevant to the process such as addresses of instructions as well as privileges for the process.  For the purpose of this assignment, it is set to an integer value since no actual process data is being created yet.

\subsection{Page Table}
This element will hold information about which page table the current process is using.  For this assignment also, we will not be using this field since no actual process data will be used in the system.

\subsection{Previous Index}
This is a pointer in the linked list implementation of the queue pointing to the previous element in the queue.  This is used to help enqueue and dequeue elements onto the queue and keep track of where elements are in relationship to the head and tail of the queue.  The head of the queue will have a previous index value of -1, indicating that there is nothing else in the queue before it.  The head of the queue will be where elements are dequeued from.

\subsection{Next Index}
This is a pointer in the linked list implementation of the queue pointing to the next element in the queue.  This is used to help enqueue and dequeue elements onto the queue and keep track of where elements are in relationship to the head and tail of the queue.  The tail of the queue will have a next index value of -1, indicating that there is nothing after this element in the queue.  The tail of the queue will be where elements are enqueued.  

\subsection{Registers}
These registers will hold any register values that may be needed by the process and allow for information about condition codes and general-purpose registers being used by this process.  Again for this assignment, there will be no actual data put into these registers.

\subsection{Priority}
The Priority field will be used for the Priority Scheduling scheme when it is implemented and else set to zero for the Round Robin scheduler.   The priority will be based on a 1 to 5 scale system where 5 is the highest priority and 1 is the lowest priority.  The process with the highest priority will be scheduled next for the Running queue.

\subsection{TQ}
The Time Quantum field will be used for the Round Robin Scheduling scheme.  This will keep track of how long a process has been placed in the running queue.  For the purposed of this lab, a time quantum will be incremented each time GO is called.  The longest a process can be in the running queue at a time will be 3 GOs, indicating that the Maximum Time Quantum will be 3 calls.  Once the process leaves the Running queue, the TQ field will be set back to 0.  

\subsection{Counter}
This counter variable is used to keep track of how long a process has been in the Ready queue for the Priority scheduler.  When the counter hits its maximum count, it will assume that the process has been in the Ready queue too long, or starving, and will increase in priority in order to give it a chance to be run on the processor.  This counter will be reset once it leaves the Ready queue or hits its maximum counter limit and increases in priority.  


\section{Scheduling Algorithms}

\subsection{Fair-Share (Round Robin)}
%this is how to add a figure with the [H] explicitly telling the compiler that this figure is to appear
%specifically here in the text
\begin{figure}[H]
%this is how to center something
\begin{center}
%the image is called by name and must be in the same folder that this file is in,
%otherwise ../.. will be required to tell the program where to get the image from
\includegraphics[scale=.50]{RoundRobin.jpg}
%how to add a caption below an image
\caption{Figure 3.1.1: Fair-Share Execution Flow Diagram}
\end{center}
\end{figure}
The fair-share algorithm will be seperated into 4 groups and the max time quantum will be found by taking the least common multiple (LCM) of all the groups. There are 4 groups for debuging purposes to be able to test out the fairness of the max time quantum implementation but can be scaled to a different size with minimal changes to the code. LCM is used to find the max TQ so that the Max TQ can be divided between processes in a group evenly.

The scheduler will start when it receives the GO command from the testing interface by checking if there is a process currently. If not, it will increase the process' time quantum by 1 and finish until GO is called. If so, it checks if that process has reached the maximum TQ for its group and if it has it will reset that processes' TQ then call EOQUANTUM on that process. This will allow the Max TQ to be updated only if there was a new process created since the last process was put on the running queue, this is done with a boolean that will get set to true when a process is created. This is done to allow each process to get its fair amount of time in the running state. A process is then dequeued from the head of the ready queue and enqueued into the running queue. Then the scheduler is done until another input is received from the scheduler.

\subsection{Priority Scheduling}
\begin{figure}[H]
\begin{center}
\includegraphics[scale=.50]{Priority.jpg}
\caption{Figure 3.2.1: Priority Execution Flow Diagram}
\end{center}
\end{figure}
The priority scheduling will work based on a scale of ''1 - 2 - 3 - 4 - 5'' which corresponds to ''Low:1 - Normal:3 - High:5''. The queue will be able to handle multiple processes with the same process in a fair way to be explained in the following paragraph. The priority of the process will be assigned during the “create” command in the testing interface and will be given a priority of 3.  This will be to make sure that every process given to the scheduler will start off the same.

The scheduler will start by checking if a process is running when the GO command is received from the Testing Interface.  If there is, the Scheduler will leave that process in the Running state to finish out its time quantum and will return control back to the Testing Interface.  This process will stay in there until it receives an EOLIFE, EOQUANTUM, WAIT or hits the maximum time quantum of the system.  If the process in the Running queue has finished with EOLIFE, will be moved to the Terminate queue. Otherwise, if there is no process in the Running queue and the Ready queue is not empty, the scheduler will look through the Ready queue for the process with the highest priority and will move the first found process (if multiple processes with the same priority) to the ready queue. 

If the process leaves the Running queue before it hits the maximum time quantum, it will assume that the process is interactive and increase its priority to give it a higher priority for the processor when it is moved back to the Ready queue.  If the process uses up the whole time quantum allowed for the processor, its priority will decrease indicating that this process is more compute bound and will move it back to the Ready queue to give processor time to other processes with higher priority.  These operations are constant time increase or descrease the priorities.  

To prevent starvation of processes that decrease to priority 1 for being computer bound, the counter field in the PCB will be used to keep track of how long the process has been in the ready.  If the process has been in the ready Queue for 10 go calls, the scheduler will increase the priority of the process in order to give it a chance to be placed on the processor.  The counters will be increased for every go call that is made and therefore this process in O(n) to increase the counters for all the processes in the Ready queue.  The counter will be reset once it leaves the Ready queue or if it hits the maximum count and the priority is increased.  



\section{Process Manager}
The process manager will receive transitions from the Scheduler and will declare the following state Queues:
%this is how to start a bullet list
\begin{itemize}
%add a new item inside
\item New
%nest another begin in order to begin a tabbed list, this can be done multiple times
\begin{itemize}
\item The New queue will actually create the process struct and store that information in the new queue while waiting transfer to the ready queue.
\end{itemize}

\item Ready
\begin{itemize}
\item The Ready queue holds a process inside of its queue until the running state is ready to run a new process.
\end{itemize}

\item Running
\begin{itemize}
\item The Running queue will hold one process that was dequeued from the ready state and will keep that process running until an interrupt occurs.
\end{itemize}

\item Wait
\begin{itemize}
\item The Wait queue will hold the processes from the running state that called for an interrupt.
\end{itemize}

\item Terminate
\begin{itemize}
\item The Terminate queue will hold any processes that have completed their execution time on the processor and will be erased from the program.  The PIDs will remain in order to reuse them for new processes.
\end{itemize}

\end{itemize}

The Process Manager will run linearly based on the single-core processor limit and handle moving a process between queues. In order to do this, the manager dequeues the process to be moved and holds it in local memory temporarily. The process is then enqueued onto the  queue it was to be placed in and removed from temporary memory. Once a process has been created in the system, it will be dequeued from the New queue and enqueued onto the Ready queue right away. In these states, the process manager waits for an interrupt from the testing interface which includes:

\begin{itemize}
\item GO
\begin{itemize}
\item The GO command will call the scheduler that is being run at the time to place the next process onto the running queue.  This is described in the Scheduler section of the document of how it is implemented.
\end{itemize}

\item WAIT
\begin{itemize}
\item The process needs to wait for resources and is moved from the Running to the Wait queue until the process is called by UNWAIT.
\end{itemize}

\item UNWAIT
\begin{itemize}
\item Resources that a specific process needs is available allowing that specific process to be moved from the Wait queue to the Ready queue.
\end{itemize}

\item EOQUANTUM
\begin{itemize}
\item The process is moved from the running queue back into the ready queue because its allocated CPU time is finished.
\end{itemize}

\item EOLIFE
\begin{itemize}
\item The process is moved from the running queue to the terminated queue because it is being terminated. After the interrupt, the processes in the Terminate queue are kept to be used again for later processes that need to reuse a PID and then will be deleted.
\end{itemize}

\end{itemize}


\section{Misc. Design Decisions}
\subsection{Process Manager Changes}
%subsubsection is the , well you should be able to figure it out
\subsubsection{QueueSize}
For this program, each queue in the Process Manager will hold a max of 20 processes each queue except for the Running state which will only hold one.  A max of 20 processes is only allowed in the system at a time to keep room in the queues for different transitions.  This was to simplify the project for now and the number of processes will increase as the OS becomes more advanced.

\subsubsection {Reuseable PIDs}
In order to ensure that no duplicate PIDs are used in the system, the Process Manager will increment PIDs by a counter and will assign the PID to the new process.  However, once a process has terminated, the terminated PID will be stored in the Terminate queue and once a new process needs to be created, it will first check to see if there is a usable PID in the list to be assigned to the new process.  If there is not, the counter will increment and be assigned to the new process.  This will ensure that no duplicate PIDs will be used as well as reuse old PIDs that were in the system to be sure that the counter does not run out of integers.  Once the PID is reused from the Terminate queue, it will be deleted from the Terminate queue.

\subsubsection {Creating a Process}
When a process is being created, instead of waiting for a GO command to move the new process from the New queue to the Ready queue, the new process will be moved right away after it is created.  The New queue will still be used to create the process but will only hold it momentarily.  

\subsubsection {Initializing Queue when it is Empty}
Due to time restraints,  an issue can up in our free list for the queues and the pointers being rearranged when the queues hit the maximum capacity.  When the queues hit the maxiumum capacity, the free list would not be connected anymore and when processes were trying to enqueue back onto the list, the linked list for the queue was not pointing to the right elements.  For this reason, we initialize the queue every time the queue becomes empty.  This involves the free list being recreated by arranging the pointers for the whole linked list and resetting the head and tail for the queue.  This is a temporary solution to this problem for this assignment until the bug can be fixed.  This process is O(n) to clear the one queue.

\section{Test Cases}
Below describes the test cases we will be focusing on for this assignment.  We have already tested the functionality of the Queue Manager and the Process Manager so we will just be focusing on the robustness of the Scheduler.

\subsection{Testing Interface}
\begin{itemize}
\item Make sure we can select a scheduler when the program starts up with Init\_Sched.
\item Make sure what ever scheduler is selected, it will load that portion of the program and clear all queues.
\item Make sure we can create a process with the new fields with Create\_Proc.
\item Make sure the List functions list the correct queues.
\item Make sure the LIst functions lists the PIDs in an ordered fashion.
\item Make sure the GO functions called the Scheduler Module to implement the scheduler.
Round 
\end{itemize}

\subsection{Round Robin}
\begin{itemize}
\item Make sure the time quantum is even between all processes and is removed from running once the max TQ is hit. 
\item Make sure the time quantum gets incremented for the process in Running after each GO.
\item Make sure the TQ field in the PCB gets reset when the process gets removed from the Running state.
\item Make sure the head of the Ready queue is the next process for execution for the Running queue.
\item If there is no process in the Ready queue when GO is called and nothing running, report an error.
\end{itemize}

\subsection{Priority}
\begin{itemize}
\item Takes the first highest priority in the ready queue because we can have multiple of the same priority as stated above.
\item If there are no processes in the Ready queue, it will return an error.
\item Make sure the process stays in the Running state if it has not been terminated or interrupted by the Testing Interface. 
\end{itemize}

\subsection{Other}
\begin{itemize}
\item Make sure that the PID is unique for each process
\item The Terminate queue sends PID to Testing Interface that has been terminated to be reused for another process.
\end{itemize}


\section{Run Time}
The run time for the Priority Queue will be O(n) because using highest priority scheduling the scheduler will have to run through the Ready queue to find the highest priority so it can go to the running queue to be executed by the CPU. This was done to keep the same formatting as the rest of the labs without having to add more queues to separate the priorities to find them in O(1).  Since there is only allowed a maximum of 20 processes in the system, this will not be that time consuming for now until we begin to allow more processes.  We are assuming that this same amount of processes will be used in the system for the rest of the labs in order to simply testing the OS for presentations and to make it easier to debug the system with a small amount of processes. The rest of the functions used for the Priority queue are constant time, O(1), for priority assigning but also O(n) to increase the priorities for the processes that are being starved in the ready Queue since it has to check for every GO function to increase the counter for the process.  Overall, the running time for the Priority Queue is O(n).  In the future if this becomes a problem, we can implement multiple queues to hold the different process priorities in order to change the runtime of searching for the priority to O(1) but increasing the priorities for the starving processes will most likely stay at O(n) since we will have to keep checking each process to see if it is being starved.

For the Fair Share Group algorithm, it will remain constant time because it goes through the queues as the original Priority Queue that was created in Lab 2. Everything in the Fair Share Group algorithm runs in constant time because other than adding LCM the logic is fairly unchanged from the previous lab and does not loop through the list. LCM runs in constant time because it is a predefined set of commands that are only called after a new process is added and there is no running process.
\end{document}